MUSIC (algorithm)
   HOME

TheInfoList



OR:

MUSIC (multiple sIgnal classification) is an algorithm used for frequency estimation and
radio direction finding Direction finding (DF), radio direction finding (RDF), or radiogoniometry is the use of radio waves to determine the direction to a radio source. The source may be a cooperating radio transmitter or may be an inadvertent source, a natural ...
.Schmidt, R.O,
Multiple Emitter Location and Signal Parameter Estimation
" IEEE Trans. Antennas Propagation, Vol. AP-34 (March 1986), pp. 276–280.


History

In many practical signal processing problems, the objective is to estimate from measurements a set of constant parameters upon which the received signals depend. There have been several approaches to such problems including the so-called maximum likelihood (ML) method of Capon (1969) and Burg's maximum entropy (ME) method. Although often successful and widely used, these methods have certain fundamental limitations (especially bias and sensitivity in parameter estimates), largely because they use an incorrect model (e.g., AR rather than special
ARMA Arma, ARMA or variants, may refer to: Places * Arma, Kansas, United States * Arma, Nepal * Arma District, Peru * Arma District, Yemen * Arma Mountains, Afghanistan People * Arma people, an ethnic group of the middle Niger River valley * Arma lan ...
) of the measurements. Pisarenko (1973) was one of the first to exploit the structure of the data model, doing so in the context of estimation of parameters of complex sinusoids in additive noise using a covariance approach. Schmidt (1977), while working at Northrop Grumman and independently Bienvenu and Kopp (1979) were the first to correctly exploit the measurement model in the case of
sensor array A sensor array is a group of sensors, usually deployed in a certain geometry pattern, used for collecting and processing electromagnetic or acoustic signals. The advantage of using a sensor array over using a single sensor lies in the fact that an ...
s of arbitrary form. Schmidt, in particular, accomplished this by first deriving a complete geometric solution in the absence of noise, then cleverly extending the geometric concepts to obtain a reasonable approximate solution in the presence of noise. The resulting algorithm was called ''MUSIC (multiple signal classification)'' and has been widely studied. In a detailed evaluation based on thousands of simulations, the Massachusetts Institute of Technology's Lincoln Laboratory concluded in 1998 that, among currently accepted high-resolution algorithms, MUSIC was the most promising and a leading candidate for further study and actual hardware implementation. However, although the performance advantages of MUSIC are substantial, they are achieved at a cost in computation (searching over parameter space) and storage (of array calibration data).


Theory

MUSIC method assumes that a signal vector, \mathbf, consists of p complex exponentials, whose frequencies \omega are unknown, in the presence of Gaussian white noise, \mathbf, as given by the linear model : \mathbf = \mathbf \mathbf + \mathbf. Here \mathbf = mathbf(\omega_1), \cdots, \mathbf(\omega_p)/math> is an M \times p Vandermonde matrix of steering vectors \mathbf(\omega) = , e^, e^, \ldots, e^T and \mathbf = _1, \ldots, s_pT is the amplitude vector. A crucial assumption is that number of sources, p, is less than the number of elements in the measurement vector, M, i.e. p < M. The M \times M autocorrelation matrix of \mathbf is then given by :\mathbf_x = \mathbf \mathbf_s \mathbf^H + \sigma^2 \mathbf, where \sigma^2 is the noise variance, \mathbf is M \times M identity matrix, and \mathbf_s is the p \times p autocorrelation matrix of \mathbf. The autocorrelation matrix \mathbf_x is traditionally estimated using sample correlation matrix :\widehat_x = \frac \mathbf \mathbf^H where N > M is the number of vector observations and \mathbf = mathbf_1, \mathbf_2, \ldots, \mathbf_N/math>. Given the estimate of \mathbf_x, MUSIC estimates the frequency content of the signal or autocorrelation matrix using an
eigenspace In linear algebra, an eigenvector ( ) or characteristic vector is a Vector (mathematics and physics), vector that has its direction (geometry), direction unchanged (or reversed) by a given linear map, linear transformation. More precisely, an e ...
method. Since \mathbf_x is a Hermitian matrix, all of its M eigenvectors \ are orthogonal to each other. If the eigenvalues of \mathbf_x are sorted in decreasing order, the eigenvectors \ corresponding to the p largest eigenvalues (i.e. directions of largest variability) span the signal subspace \mathcal_S. The remaining M-p eigenvectors correspond to eigenvalue equal to \sigma^2 and span the noise subspace \mathcal_N, which is orthogonal to the signal subspace, \mathcal_S \perp \mathcal_N . Note that for M = p + 1, MUSIC is identical to Pisarenko harmonic decomposition. The general idea behind MUSIC method is to use all the eigenvectors that span the noise subspace to improve the performance of the Pisarenko estimator. Since any signal vector \mathbf that resides in the signal subspace \mathbf \in \mathcal_S must be orthogonal to the noise subspace, \mathbf \perp \mathcal_N, it must be that \mathbf \perp \mathbf_i for all the eigenvectors \_^M that spans the noise subspace. In order to measure the degree of orthogonality of \mathbf with respect to all the \mathbf_i \in \mathcal_N, the MUSIC algorithm defines a squared norm :d^2 = \, \mathbf_N^H \mathbf \, ^2 = \mathbf^H \mathbf_N \mathbf_N^H \mathbf = \sum_^ , \mathbf^ \mathbf_i, ^2 where the matrix \mathbf_N = mathbf_, \ldots, \mathbf_/math> is the matrix of eigenvectors that span the noise subspace \mathcal_N. If \mathbf \in \mathcal_S, then d^2 = 0 as implied by the orthogonality condition. Taking a reciprocal of the squared norm expression creates sharp peaks at the signal frequencies. The frequency estimation function for MUSIC (or the pseudo-spectrum) is :\hat P_(e^) = \frac = \frac, where \mathbf_i are the noise eigenvectors and :\mathbf = \begin1 & e^ & e^ & \cdots & e^\end^T is the candidate steering vector. The locations of the p largest peaks of the estimation function give the frequency estimates for the p signal components : \hat = \arg\max_\omega \; \hat P_(e^). MUSIC is a generalization of Pisarenko's method, and it reduces to Pisarenko's method when M=p+1. In Pisarenko's method, only a single eigenvector is used to form the denominator of the frequency estimation function; and the eigenvector is interpreted as a set of
autoregressive In statistics, econometrics, and signal processing, an autoregressive (AR) model is a representation of a type of random process; as such, it can be used to describe certain time-varying processes in nature, economics, behavior, etc. The autoregre ...
coefficients, whose zeros can be found analytically or with polynomial root finding algorithms. In contrast, MUSIC assumes that several such functions have been added together, so zeros may not be present. Instead there are local minima, which can be located by computationally searching the estimation function for peaks.


Dimension of signal space

The fundamental observation MUSIC and other subspace decomposition methods are based on is about the rank of the autocorrelation matrix \mathbf_x which is related to number of signal sources p as follows. If the sources are complex, then M > p and the dimension of the signal subspace \mathcal_S is p. If sources are real, then M > 2p and dimension of the signal subspace is 2p, i.e. each real sinusoid is generated by two base vectors. This fundamental result, although often skipped in spectral analysis books, is a reason why the input signal can be distributed into p signal subspace eigenvectors spanning \mathcal_S (2p for real valued signals) and noise subspace eigenvectors spanning \mathcal_N . It is based on signal embedding theory and can also be explained by the topological theory of manifolds.


Comparison to other methods

MUSIC outperforms simple methods such as picking peaks of DFT spectra in the presence of noise, when the number of components is known in advance, because it exploits knowledge of this number to ignore the noise in its final report. Unlike DFT, it is able to estimate frequencies with accuracy higher than one sample, because its estimation function can be evaluated for any frequency, not just those of DFT bins. This is a form of
superresolution Super-resolution imaging (SR) is a class of techniques that improve the image resolution, resolution of an digital imaging, imaging system. In optical SR the diffraction-limited, diffraction limit of systems is transcended, while in geometrical SR ...
. Its chief disadvantage is that it requires the number of components to be known in advance, so the original method cannot be used in more general cases. Methods exist for estimating the number of source components purely from statistical properties of the autocorrelation matrix. See, e.g. In addition, MUSIC assumes coexistent sources to be uncorrelated, which limits its practical applications. Recent iterative semi-parametric methods offer robust
superresolution Super-resolution imaging (SR) is a class of techniques that improve the image resolution, resolution of an digital imaging, imaging system. In optical SR the diffraction-limited, diffraction limit of systems is transcended, while in geometrical SR ...
despite highly correlated sources, e.g., SAMV


Other applications

A modified version of MUSIC, denoted as ''time-reversal MUSIC'' (TR-MUSIC) has been recently applied to computational time-reversal imaging. MUSIC algorithm has also been implemented for fast detection of the DTMF frequencies (
dual-tone multi-frequency signaling Dual-tone multi-frequency (DTMF) signaling is a telecommunication signaling system using the voice-frequency band over telephone lines between telephone equipment and other communications devices and Automatic telephone exchange, switching center ...
) in the form of C library - libmusic (including for MATLAB implementation).{{cite web , title=libmusic_m : MATLAB implementation, url=https://dataandsignal.com/software/libmusic_m , website=Data and Signal , id=MathWorks , date=2023


See also

* Spectral density estimation * Periodogram *
Matched filter In signal processing, the output of the matched filter is given by correlating a known delayed signal, or ''template'', with an unknown signal to detect the presence of the template in the unknown signal. This is equivalent to convolving the unkn ...
* Welch's method * Bartlett's method * SAMV (algorithm) *
Radio direction finding Direction finding (DF), radio direction finding (RDF), or radiogoniometry is the use of radio waves to determine the direction to a radio source. The source may be a cooperating radio transmitter or may be an inadvertent source, a natural ...
* Pitch detection algorithm * High-resolution microscopy


References


Further reading

* The estimation and tracking of frequency, Quinn and Hannan, Cambridge University Press 2001. Digital signal processing